1. Field of the Invention
The present invention relates to a method and apparatus for segmenting 3D and higher dimensional images into two subsets in order to locate a part thereof, and in particular, to a method of segmenting without any topological restriction on the resultant subsets.
2. Description of Related Art
A situation often occurs that a multi-dimensional array that assigns data to each multi-dimensional slot (voxel) is given and a need arises to partition the set of voxels into two or more subsets according to the data.
For instance, it is well known to obtain three-dimensional arrays of data representing one or more physical properties at regular grid positions within the interior of solid bodies. Such data may be obtained by non-intrusive methods such as computed axial tomography (CAT) systems, by magnetic resonance imaging (MRI) systems, or by other non-intrusive mechanisms such as ultrasound, positron emission tomography (PET), emission computed tomography (ECT) and multi-modality imaging (MMI). Each of these techniques produces a planar, grid-like array of values for each of a succession of slices of the solid object, thus providing a three-dimensional array of such values. Typically, the solid object is a human body or a portion thereof, although the method is equally applicable to other natural or artificial bodies. In the case of CAT scanning, the physical value is the coefficient of x-ray absorption. For MRI, the physical values are the spin—spin and the spin-lattice relaxation echoes. In any event, the measured physical values reflect the variations in composition, density or surface characteristics of the underlying physical structures.
It is likewise known to utilize such three-dimensional arrays of interior physical values to generate visual images of the interior structures within the body. In the case of the human body, the visual images thus produced can be used for medical purposes such as diagnostics or for the planning of surgical procedures. In order to display two-dimensional images of such three-dimensional interior structures, however, it is necessary to locate the position of the boundary of such structure within the array of physical values. A significant problem in displaying such internal surfaces is, therefore, the need to segment the data samples into the various tissues. This has been accomplished in the prior art by simply deciding the structure to which each voxel belongs by comparing the data associated to the voxel to a single threshold value, or to a range of threshold values, corresponding to the physical property values associated with each structure or its boundary. Bones or any other tissue, for example, can be characterized by a known range of density values to which the array values can be compared. Such simple thresholding, however, is too susceptible to noise. That is, at the boundary, voxels with values near threshold can be swayed either way by a smallest noise, giving very noisy result. What is needed is to incorporate the tendency of nearby voxels to belong to the same partition.
Domains of applications of segmentation other than medical applications include graphics, visualization tools, and reconstruction of 3D objects. In graphics, it is known to segment an object from an image. When there is a sequence of image (video), it can be considered a 3D image. Thus a segmentation of moving object from a video sequence is an application of 3D segmentation.
Also, the data array is not limited to 3D. Higher dimensional applications include four-dimensional segmentation of a temporal sequence of 3D images, such as a 3D image of beating heart.
It is important in many applications that the resultant sets of voxels are not restricted in the number of connected component. Indeed, it is generally necessary to be able to automatically choose the appropriate number of connected components. Moreover, for a larger class of applications, the subsets should have no topological restrictions at all. For instance, each connected component should be allowed to have as many holes as appropriate to fit the data. Conventional methods have at least one of the following three shortcomings: they either i) have topological restrictions on the solution, ii) are not guaranteed to reach the optimal solution, or iii) need user help or intervention. Some methods presuppose the nature of the set to be found. For instance, if arteries are expected, some methods try to find one-dimensional object with some thickness, making it difficult to find bifurcating arteries. An algorithm that has desirable topological properties is suggested in [O. Faugeras and R. Keriven. “Complete Dense Stereovision Using Level Set Methods”, in Proceedings of the 5th European Conference on Computer Vision, Springer-Verlag. LNCS 1406, pp. 379–393, 1998], based on an entirely different method (Level Sets of Evolution Equations). Yet, it is a gradient-descent method with no guarantee to reach the optimal. Region Growing methods, similarly, have good topological properties, but require user intervention to select the regions. Moreover, no Region Growing method is an optimization method, that is, they are not guaranteed to give optimum solutions. Another technique described in [J. Shi and J. Malik. “Normalized cuts and image segmentation.” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition 1997, pp. 731–737] uses a graph technique, which approximates the solution (i.e., it is not guaranteed), and perhaps does not have the same topological properties. The present method uses similar technique used in other area, 2D image restoration, described in [D. M. Greig, B. T. Porteous, and A. H. Seheult. “Exact maximum a posteriori estimation for binary images.” Journal of Royal Statistical Society B, 51, pp. 271–279, 1989].